/*
 * @lc app=leetcode.cn id=460 lang=cpp
 *
 * [460] LFU 缓存
 */

// @lc code=start
struct Node {
  int key, val, feq;
  Node *prev, *next;
  Node(int k, int v)
      : key(k)
      , val(v)
      , feq(1)// 默认使用一次
      , prev(nullptr)
      , next(nullptr)
  {}
};

class DLQueue
{
private:
  int size;
  Node *head, *tail;

public:
  DLQueue()
      : size(0)
  {
    head = new Node(-1, -1);
    tail = new Node(0, 0);
    head->next = tail;
    tail->prev = head;
  }

  void Enqueue(Node* node)
  {
    Link(node, tail->prev, tail);
    ++size;
  }

  Node* Dequeue()
  {
    if (size > 0) {
      Node* tmp = head->next;
      Drop(tmp);
      return tmp;
    }
    return nullptr;
  }

  // Node不是队列中的节点将导致空指针异常
  void Drop(Node* node)
  {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    --size;
  }

  void Link(Node* m, Node* p, Node* n)
  {
    m->prev = p;
    p->next = m;
    m->next = n;
    n->prev = m;
  }

  bool Empty()
  {
    return size == 0;
  }
};

class LFUCache
{
public:
  int n, N;
  int lfu;
  unordered_map<int, Node*> nodes;
  unordered_map<int, DLQueue*> multi_queue;

  LFUCache(int capacity)
      : n(0)
      , N(capacity)
      , lfu(1)
      , nodes(unordered_map<int, Node*>())
      , multi_queue(unordered_map<int, DLQueue*>())
  {}

  int get(int key)
  {
    if (N == 0)
      return -1;
    auto itr = nodes.find(key);
    if (itr == nodes.end())// key 不存在
      return -1;
    else {
      Node* node = itr->second;
      DropAndGrow(node);
      return node->val;
    }
  }

  void put(int key, int value)
  {
    if (N == 0)
      return;
    auto itr = nodes.find(key);
    if (itr != nodes.end()) {// key 已经存在，更新即可
      Node* node = itr->second;
      node->val = value;
      DropAndGrow(node);
    }
    else {
      Node* new_node = new Node(key, value);
      if (n < N) {// 容量足够，此处更新n即可
        ++n;
      }
      else {
        Node* del = multi_queue[lfu]->Dequeue();
        nodes.erase(del->key);// 从nodes里删除
        delete del;
      }
      // 新插入的节点使用次数为1次，因此更新lfu
      lfu = 1;
      nodes[key] = new_node;
      if (multi_queue.find(1) == multi_queue.end())
        multi_queue[1] = new DLQueue();
      multi_queue[1]->Enqueue(new_node);
    }
  }

  void DropAndGrow(Node* node)
  {
    // 将node从原来的队列中删除
    multi_queue[node->feq]->Drop(node);
    // 如果此次删除操作是在最少使用的队列上操作的而且导致队列为空，则更新lfu
    if (lfu == node->feq && multi_queue[lfu]->Empty())
      ++lfu;
    // 将key的使用次数+1并写回多级队列
    node->feq += 1;
    if (multi_queue.find(node->feq) == multi_queue.end())
      multi_queue[node->feq] = new DLQueue();
    multi_queue[node->feq]->Enqueue(node);
  }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end
